{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[==========] Running 10 tests from 1 test suite.\n",
      "[----------] Global test environment set-up.\n",
      "[----------] 10 tests from MazeSearchTest\n",
      "[ RUN      ] MazeSearchTest.BreadthFirstSearchFindsShortestPath\n",
      "[       OK ] MazeSearchTest.BreadthFirstSearchFindsShortestPath (0 ms)\n",
      "[ RUN      ] MazeSearchTest.DepthFirstSearchProducesNonShorterPathThanBfs\n",
      "[       OK ] MazeSearchTest.DepthFirstSearchProducesNonShorterPathThanBfs (0 ms)\n",
      "[ RUN      ] MazeSearchTest.BlockedEntranceReturnsEmptyForBothAlgorithms\n",
      "[       OK ] MazeSearchTest.BlockedEntranceReturnsEmptyForBothAlgorithms (0 ms)\n",
      "[ RUN      ] MazeSearchTest.BreadthFirstSearchNavigatesComplexCorridor\n",
      "[       OK ] MazeSearchTest.BreadthFirstSearchNavigatesComplexCorridor (0 ms)\n",
      "[ RUN      ] MazeSearchTest.DepthFirstSearchRespectsRightFirstPriority\n",
      "[       OK ] MazeSearchTest.DepthFirstSearchRespectsRightFirstPriority (0 ms)\n",
      "[ RUN      ] MazeSearchTest.BreadthFirstSearchOpenGridHasMinimalLength\n",
      "[       OK ] MazeSearchTest.BreadthFirstSearchOpenGridHasMinimalLength (0 ms)\n",
      "[ RUN      ] MazeSearchTest.BreadthFirstSearchDetectsNoPathWhenExitIsTrapped\n",
      "[       OK ] MazeSearchTest.BreadthFirstSearchDetectsNoPathWhenExitIsTrapped (0 ms)\n",
      "[ RUN      ] MazeSearchTest.LargeMazeWithDeadEndsPrefersShortestRoute\n",
      "[       OK ] MazeSearchTest.LargeMazeWithDeadEndsPrefersShortestRoute (0 ms)\n",
      "[ RUN      ] MazeSearchTest.BreadthFirstSearchHandlesMultipleOptimalRoutes\n",
      "[       OK ] MazeSearchTest.BreadthFirstSearchHandlesMultipleOptimalRoutes (0 ms)\n",
      "[ RUN      ] MazeSearchTest.SingleCellMazeReturnsTrivialPath\n",
      "[       OK ] MazeSearchTest.SingleCellMazeReturnsTrivialPath (0 ms)\n",
      "[----------] 10 tests from MazeSearchTest (0 ms total)\n",
      "\n",
      "[----------] Global test environment tear-down\n",
      "[==========] 10 tests from 1 test suite ran. (0 ms total)\n",
      "[  PASSED  ] 10 tests.\n"
     ]
    }
   ],
   "source": [
    "! g++ -std=c++17 -O2 maze_search_test.cpp -lgtest -lgtest_main -lgmock -pthread -o maze_search_test && ./maze_search_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 广度优先搜索（breadthFirstSearch）\n",
    "\n",
    "- 想像迷宫是一张方格纸，从左上角要走到右下角。\n",
    "- 我们像排队一样，一圈一圈地往外走：先走离起点一步的格子，再走离起点两步的格子……\n",
    "- 每走到一个新格子，就记下“我是从哪个格子走过来的”。\n",
    "- 一旦我们排队排到终点，就沿着这些记录，倒着找回去，把整条最短路线拼出来。\n",
    "- 因为我们是按“步数由少到多”的顺序探索，所以找到的路线一定是最短的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 代码实现"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 1：写出函数框架和基本检查"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <queue>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  // 先把函数名字、输入、输出写好，并检查迷宫是不是空的。\n",
    "  if (maze.empty() || maze[0].empty()) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 这里之后再补充真正的搜索逻辑\n",
    "  return {};\n",
    "}\n",
    "\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 2：准备需要的变量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <queue>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  // 先把函数名字、输入、输出写好，并检查迷宫是不是空的。\n",
    "  if (maze.empty() || maze[0].empty() || maze[0][0] == 1) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 补充行数列数、访问标记、前驱数组（用来回溯最短路）和一个队列。\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<bool> visited(rows * cols, false);\n",
    "  std::vector<int> parent(rows * cols, -1);\n",
    "  std::queue<Cell> q;\n",
    "\n",
    "  // 留待后面用的函数和循环\n",
    "  return {};\n",
    "}\n",
    "\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 3：写一个“能不能走”的检查小工具"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <queue>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  // 先把函数名字、输入、输出写好，并检查迷宫是不是空的。\n",
    "  if (maze.empty() || maze[0].empty() || maze[0][0] == 1) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 补充行数列数、访问标记、前驱数组（用来回溯最短路）和一个队列。\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<bool> visited(rows * cols, false);\n",
    "  std::vector<int> parent(rows * cols, -1);\n",
    "  std::queue<Cell> q;\n",
    "\n",
    "  // 用 lambda 函数判断坐标是否在界内、是否为通路。\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 留待后面用的函数和循环\n",
    "  return {};\n",
    "}\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 4：写一个把格子放进队伍的函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <queue>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  // 先把函数名字、输入、输出写好，并检查迷宫是不是空的。\n",
    "  if (maze.empty() || maze[0].empty() || maze[0][0] == 1) {\n",
    "    return {};\n",
    "  }\n",
    "  // 补充行数列数、访问标记、前驱数组（用来回溯最短路）和一个队列。\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<bool> visited(rows * cols, false);\n",
    "  std::vector<int> parent(rows * cols, -1);\n",
    "  std::queue<Cell> q;\n",
    "\n",
    "  // 用 lambda 函数判断坐标是否在界内、是否为通路。\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 同时标记访问、记录前驱。\n",
    "  auto enqueue = [&](int r, int c, int prevIdx) {\n",
    "    if (!isValid(r, c)) {\n",
    "      return;\n",
    "    }\n",
    "    const int idx = r * cols + c;\n",
    "    if (visited[idx]) {\n",
    "      return;\n",
    "    }\n",
    "    visited[idx] = true;\n",
    "    parent[idx] = prevIdx;\n",
    "    q.push({r, c});\n",
    "  };\n",
    "\n",
    "  // 留待后面用的函数和循环\n",
    "  return {};\n",
    "}\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 5：把起点放进队伍，并写主循环"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <queue>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  // 1: 先把函数名字、输入、输出写好，并检查迷宫是不是空的。\n",
    "  if (maze.empty() || maze[0].empty() || maze[0][0] == 1) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 2: 补充行数列数、访问标记、前驱数组（用来回溯最短路）和一个队列。\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<bool> visited(rows * cols, false);\n",
    "  std::vector<int> parent(rows * cols, -1);\n",
    "  std::queue<Cell> q;\n",
    "\n",
    "  // 3: 用 lambda 函数判断坐标是否在界内、是否为通路。\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 4: 同时标记访问、记录前驱。\n",
    "  auto enqueue = [&](int r, int c, int prevIdx) {\n",
    "    if (!isValid(r, c)) {\n",
    "      return;\n",
    "    }\n",
    "    const int idx = r * cols + c;\n",
    "    if (visited[idx]) {\n",
    "      return;\n",
    "    }\n",
    "    visited[idx] = true;\n",
    "    parent[idx] = prevIdx;\n",
    "    q.push({r, c});\n",
    "  };\n",
    "\n",
    "  // 5: \n",
    "  //  起点用特殊前驱 -2 标记。\n",
    "  //  每次出队一个格子，检查是否到终点。\n",
    "  //  没到就把四个方向邻居加入队列。\n",
    "  enqueue(0, 0, -2); // 起点入队，-2 表示没有前驱\n",
    "\n",
    "  constexpr int DR[4] = {0, 1, 0, -1};\n",
    "  constexpr int DC[4] = {1, 0, -1, 0};\n",
    "\n",
    "  while (!q.empty()) {\n",
    "    const Cell current = q.front();\n",
    "    q.pop();\n",
    "\n",
    "    if (current.row == rows - 1 && current.col == cols - 1) {\n",
    "      // 先不写回溯，下一步补\n",
    "    }\n",
    "\n",
    "    const int curIdx = current.row * cols + current.col;\n",
    "    for (int i = 0; i < 4; ++i) {\n",
    "      enqueue(current.row + DR[i], current.col + DC[i], curIdx);\n",
    "    }\n",
    "  }\n",
    "\n",
    "  // 留待后面用的函数和循环\n",
    "  return {};\n",
    "}\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 5：把起点放进队伍，并写主循环"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <algorithm>\n",
    "#include <queue>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  // 1: 先把函数名字、输入、输出写好，并检查迷宫是不是空的。\n",
    "  if (maze.empty() || maze[0].empty() || maze[0][0] == 1) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 2: 补充行数列数、访问标记、前驱数组（用来回溯最短路）和一个队列。\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<bool> visited(rows * cols, false);\n",
    "  std::vector<int> parent(rows * cols, -1);\n",
    "  std::queue<Cell> q;\n",
    "\n",
    "  // 3: 用 lambda 函数判断坐标是否在界内、是否为通路。\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 4: 同时标记访问、记录前驱。\n",
    "  auto enqueue = [&](int r, int c, int prevIdx) {\n",
    "    if (!isValid(r, c)) {\n",
    "      return;\n",
    "    }\n",
    "    const int idx = r * cols + c;\n",
    "    if (visited[idx]) {\n",
    "      return;\n",
    "    }\n",
    "    visited[idx] = true;\n",
    "    parent[idx] = prevIdx;\n",
    "    q.push({r, c});\n",
    "  };\n",
    "\n",
    "  // 5: \n",
    "  //  起点用特殊前驱 -2 标记。\n",
    "  //  每次出队一个格子，检查是否到终点。\n",
    "  //  没到就把四个方向邻居加入队列。\n",
    "  enqueue(0, 0, -2); // 起点入队，-2 表示没有前驱\n",
    "\n",
    "  constexpr int DR[4] = {0, 1, 0, -1};\n",
    "  constexpr int DC[4] = {1, 0, -1, 0};\n",
    "\n",
    "  while (!q.empty()) {\n",
    "    const Cell current = q.front();\n",
    "    q.pop();\n",
    "\n",
    "    if (current.row == rows - 1 && current.col == cols - 1) {\n",
    "      // 先不写回溯，下一步补\n",
    "    }\n",
    "\n",
    "    const int curIdx = current.row * cols + current.col;\n",
    "    for (int i = 0; i < 4; ++i) {\n",
    "      enqueue(current.row + DR[i], current.col + DC[i], curIdx);\n",
    "    }\n",
    "  }\n",
    "\n",
    "  return {};\n",
    "}\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 6：写回溯（从终点倒着拼最短路径）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <algorithm>\n",
    "#include <queue>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "auto breadthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  // 1: 先把函数名字、输入、输出写好，并检查迷宫是不是空的。\n",
    "  if (maze.empty() || maze[0].empty() || maze[0][0] == 1) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 2: 补充行数列数、访问标记、前驱数组（用来回溯最短路）和一个队列。\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<bool> visited(rows * cols, false);\n",
    "  std::vector<int> parent(rows * cols, -1);\n",
    "  std::queue<Cell> q;\n",
    "\n",
    "  // 3: 用 lambda 函数判断坐标是否在界内、是否为通路。\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 4: 同时标记访问、记录前驱。\n",
    "  auto enqueue = [&](int r, int c, int prevIdx) {\n",
    "    if (!isValid(r, c)) {\n",
    "      return;\n",
    "    }\n",
    "    const int idx = r * cols + c;\n",
    "    if (visited[idx]) {\n",
    "      return;\n",
    "    }\n",
    "    visited[idx] = true;\n",
    "    parent[idx] = prevIdx;\n",
    "    q.push({r, c});\n",
    "  };\n",
    "\n",
    "  // 5: \n",
    "  //  起点用特殊前驱 -2 标记。\n",
    "  //  每次出队一个格子，检查是否到终点。\n",
    "  //  没到就把四个方向邻居加入队列。\n",
    "  enqueue(0, 0, -2); // 起点入队，-2 表示没有前驱\n",
    "\n",
    "  constexpr int DR[4] = {0, 1, 0, -1};\n",
    "  constexpr int DC[4] = {1, 0, -1, 0};\n",
    "\n",
    "  while (!q.empty()) {\n",
    "    const Cell current = q.front();\n",
    "    q.pop();\n",
    "\n",
    "    if (current.row == rows - 1 && current.col == cols - 1) {\n",
    "      // 先不写回溯，下一步补\n",
    "    }\n",
    "\n",
    "    const int curIdx = current.row * cols + current.col;\n",
    "    for (int i = 0; i < 4; ++i) {\n",
    "      enqueue(current.row + DR[i], current.col + DC[i], curIdx);\n",
    "    }\n",
    "\n",
    "    // 6\n",
    "    //  根据 parent 从终点一步步往回走，压进 path。\n",
    "    //  最后 reverse 一下，得到正向路径。\n",
    "\n",
    "    if (current.row == rows - 1 && current.col == cols - 1) {\n",
    "      std::vector<Cell> path;\n",
    "      for (int idx = current.row * cols + current.col;\n",
    "          idx != -2; idx = parent[idx]) {\n",
    "        path.push_back({idx / cols, idx % cols});\n",
    "      }\n",
    "      std::reverse(path.begin(), path.end());\n",
    "      return path;\n",
    "    }\n",
    "  }\n",
    "\n",
    "  return {};\n",
    "}\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 深度优先搜索（depthFirstSearch）\n",
    "\n",
    "- 这个方法像是在迷宫里一直往前冲，直到碰壁才回头。\n",
    "- 从起点开始，按照固定顺序（向右、向下、向左、向上）试着走。\n",
    "- 如果一个方向能走，就继续往那个方向走；如果走到死胡同，就退一步，换下一个方向再试。\n",
    "- 只要有路线能到终点，就会把整条路记录下来，但不一定是最短的（因为可能先走了绕远的路）。\n",
    "- 当四个方向都试过还不行，就回到上一个格子继续找别的路。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 1：写出函数框架和初步检查"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <functional>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "// 1. 先把函数结构写好\n",
    "auto depthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  if (maze.empty() || maze[0].empty()) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 后续补充\n",
    "  return {};\n",
    "}\n",
    "\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 2：准备变量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <functional>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "// 1. 先把函数结构写好\n",
    "auto depthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  if (maze.empty() || maze[0].empty()) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 2. 包括行数、列数、访问标记表以及一个用来保存路径的数组\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));\n",
    "  std::vector<Cell> path;\n",
    "\n",
    "  // 后续补充\n",
    "  return {};\n",
    "}\n",
    "\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 3：写“能不能走”的检查"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <functional>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "// 1. 先把函数结构写好\n",
    "auto depthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  if (maze.empty() || maze[0].empty()) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 2. 包括行数、列数、访问标记表以及一个用来保存路径的数组\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));\n",
    "  std::vector<Cell> path;\n",
    "\n",
    "  // 3. 和 BFS 类似，但这次放在 DFS 文件里\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 后续补充\n",
    "  return {};\n",
    "}\n",
    "\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 4：写递归函数 dfs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <functional>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "// 1. 先把函数结构写好\n",
    "auto depthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  if (maze.empty() || maze[0].empty()) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 2. 包括行数、列数、访问标记表以及一个用来保存路径的数组\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));\n",
    "  std::vector<Cell> path;\n",
    "\n",
    "  // 3. 和 BFS 类似，但这次放在 DFS 文件里\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 4.\n",
    "  // 判断是否能访问当前格子。\n",
    "  // 标记已访问，加入路径。\n",
    "  // 如果到终点直接返回 true。\n",
    "  // 按固定顺序（右、下、左、上）尝试四个方向。\n",
    "  // 如果都不行，撤回当前格子并返回 false。\n",
    "  std::function<bool(int, int)> dfs = [&](int r, int c) -> bool {\n",
    "    if (!isValid(r, c) || visited[r][c]) {\n",
    "      return false;\n",
    "    }\n",
    "    visited[r][c] = true;\n",
    "    path.push_back({r, c});\n",
    "\n",
    "    if (r == rows - 1 && c == cols - 1) {\n",
    "      return true;\n",
    "    }\n",
    "\n",
    "    constexpr int DR[4] = {0, 1, 0, -1};\n",
    "    constexpr int DC[4] = {1, 0, -1, 0};\n",
    "    for (int i = 0; i < 4; ++i) {\n",
    "      if (dfs(r + DR[i], c + DC[i])) {\n",
    "        return true;\n",
    "      }\n",
    "    }\n",
    "\n",
    "    path.pop_back();\n",
    "    return false;\n",
    "  };\n",
    "\n",
    "  // 后续补充\n",
    "  return {};\n",
    "}\n",
    "\n",
    "} // namespace Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 步骤 5：在主函数里调用 dfs，并决定返回什么"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "#include <functional>\n",
    "#include <vector>\n",
    "\n",
    "namespace Maze {\n",
    "\n",
    "struct Cell {\n",
    "  int row{0};\n",
    "  int col{0};\n",
    "};\n",
    "\n",
    "// 1. 先把函数结构写好\n",
    "auto depthFirstSearch(const std::vector<std::vector<int>>& maze)\n",
    "    -> std::vector<Cell> {\n",
    "  if (maze.empty() || maze[0].empty()) {\n",
    "    return {};\n",
    "  }\n",
    "\n",
    "  // 2. 包括行数、列数、访问标记表以及一个用来保存路径的数组\n",
    "  const int rows = static_cast<int>(maze.size());\n",
    "  const int cols = static_cast<int>(maze[0].size());\n",
    "  std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));\n",
    "  std::vector<Cell> path;\n",
    "\n",
    "  // 3. 和 BFS 类似，但这次放在 DFS 文件里\n",
    "  auto isValid = [&](int r, int c) noexcept {\n",
    "    return r >= 0 && c >= 0 && r < rows && c < cols && maze[r][c] == 0;\n",
    "  };\n",
    "\n",
    "  // 4.\n",
    "  // 判断是否能访问当前格子。\n",
    "  // 标记已访问，加入路径。\n",
    "  // 如果到终点直接返回 true。\n",
    "  // 按固定顺序（右、下、左、上）尝试四个方向。\n",
    "  // 如果都不行，撤回当前格子并返回 false。\n",
    "  std::function<bool(int, int)> dfs = [&](int r, int c) -> bool {\n",
    "    if (!isValid(r, c) || visited[r][c]) {\n",
    "      return false;\n",
    "    }\n",
    "    visited[r][c] = true;\n",
    "    path.push_back({r, c});\n",
    "\n",
    "    if (r == rows - 1 && c == cols - 1) {\n",
    "      return true;\n",
    "    }\n",
    "\n",
    "    constexpr int DR[4] = {0, 1, 0, -1};\n",
    "    constexpr int DC[4] = {1, 0, -1, 0};\n",
    "    for (int i = 0; i < 4; ++i) {\n",
    "      if (dfs(r + DR[i], c + DC[i])) {\n",
    "        return true;\n",
    "      }\n",
    "    }\n",
    "\n",
    "    path.pop_back();\n",
    "    return false;\n",
    "  };\n",
    "\n",
    "  // 5.\n",
    "  // 如果 dfs(0,0) 成功，就返回 path。\n",
    "  // 否则返回空数组。\n",
    "  if (dfs(0, 0)) {\n",
    "    return path;\n",
    "  }\n",
    "\n",
    "  return {};\n",
    "}\n",
    "\n",
    "} // namespace Maze"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "C++17",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
